/*
https://leetcode.cn/problems/maximum-value-at-a-given-index-in-a-bounded-array/submissions/565551945/

二分搜索

24/9/16
*/


class Solution {
public:
    // 辅助函数，检查在给定的数组长度 `arrayLength`、最大和 `maxTotalSum`、目标索引 `targetIndex` 和目标值 `targetValue` 下，
    // 是否可以构造出一个数组，使得该数组的和不超过 `maxTotalSum`
    bool canConstructArray(int arrayLength, int maxTotalSum, int targetIndex, int targetValue) {
        long totalSum = targetValue; // 初始化总和为目标值

        int leftLength = targetIndex; // 目标索引左边的长度
        int rightLength = arrayLength - targetIndex - 1; // 目标索引右边的长度

        totalSum += calculateSum(targetValue, leftLength); // 计算左边部分的和
        totalSum += calculateSum(targetValue, rightLength); // 计算右边部分的和

        return totalSum <= maxTotalSum; // 返回总和是否不超过最大和
    }

    // 辅助函数，计算从 `startValue` 开始的长度为 `length` 的递减序列的和
    long calculateSum(int startValue, int length) {
        if (length + 1 < startValue) {
            int endValue = startValue - length; // 序列的最后一个值
            return (long)(startValue - 1 + endValue) * length / 2; // 等差数列求和公式
        } else {
            int onesCount = length - (startValue - 1); // 1 的数量
            return (long)startValue * (startValue - 1) / 2 + onesCount; // 等差数列求和公式加上 1 的数量
        }
    }

    // 主函数，计算在给定数组长度 `n`、目标索引 `index` 和最大和 `maxSum` 下，目标索引处的最大值
    int maxValue(int n, int index, int maxSum) {
        if (n == 1) {
            return maxSum; // 如果数组长度为 1，直接返回最大和
        }

        // 二分查找的左右边界
        int leftBoundary = maxSum / n; // 最小可能的值
        int rightBoundary = maxSum / 2 + 1; // 最大可能的值

        while (leftBoundary <= rightBoundary) {
            int midValue = (leftBoundary + rightBoundary) >> 1; // 计算中间值

            if (canConstructArray(n, maxSum, index, midValue)) {
                leftBoundary = midValue + 1; // 如果可以构造数组，尝试更大的值
            } else {
                rightBoundary = midValue - 1; // 否则，尝试更小的值
            }
        }

        return rightBoundary; // 返回目标索引处的最大值
    }
};